package com.c2b.algorithm.newcoder;

/**
 * <a href='https://www.nowcoder.com/practice/02bf49ea45cd486daa031614f9bd6fc3?tpId=295&tqId=23286&ru=%2Fexam%2Foj&qru=%2Fta%2Fformat-top101%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj'>BM14 链表的奇偶重排</a>
 *
 * @author c2b
 * @since 2024/3/14 11:41
 */
public class BM14OddEvenList {
    public static class Solution {
        public ListNode oddEvenList(ListNode head) {
            if (head == null || head.next == null) {
                return head;
            }
            ListNode odd = head;
            ListNode evenHead = head.next;
            ListNode even = evenHead;
            while (even != null && even.next != null) {
                odd.next = even.next;
                odd = odd.next;
                even.next = odd.next;
                even = even.next;
            }
            odd.next = evenHead;
            return head;
        }
    }

    public static void main(String[] args) {
        ListNode head1 = new ListNode(1);
        head1.next = new ListNode(2);
        head1.next.next = new ListNode(3);
        head1.next.next.next = new ListNode(4);
        head1.next.next.next.next = new ListNode(5);
        head1.next.next.next.next.next = new ListNode(6);

        ListNode head2 = new ListNode(1);
        head2.next = new ListNode(4);
        head2.next.next = new ListNode(6);
        head2.next.next.next = new ListNode(3);
        head2.next.next.next.next = new ListNode(7);

        Solution solution = new Solution();
        Printer.printListNode(solution.oddEvenList(head1));
        Printer.printListNode(solution.oddEvenList(head2));
    }
}
